class Hashing {
private:
    vector<long long> p;
    vector<long long> h;
    long long mod;

public:
    Hashing(const string& word, long long base, int mod)
    {
        int n = word.size();
        p.resize(n + 1);
        h.resize(n + 1);
        p[0] = 1;
        this->mod = mod;
        for (int i = 1; i <= n; i++)
        {
            p[i] = (p[i - 1] * base) % mod;
            h[i] = (h[i - 1] * base + word[i - 1]) % mod;
        }
    }

    long long query(int l, int r)
    {
        return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
    }
};

class Solution
{
    int jump(vector<int>& nums) 
    {
        int ans = 0;
        // 这里要跳到 n 这个位置，说明要遍历到 n - 1
        // 当 i = n − 1 时，如果 i < cur，说明可以到达 n
        // 如果 i = cur，我们会造桥，这样也可以到达 n
        // 所以无论是何种情况，都只需要遍历到 n − 1。或者说，n 已经是终点了，你总不能在终点还打算造桥吧?
        int next = 0;   // 下一座桥的右端点的最大值
        int cur = 0;    // 已建造的桥的右端点
        for(int i = 0, n = nums.size(); i < n; i++)
        {
            next = max(next, i + nums[i]);
            if(cur == i)        // 到达已建造的桥的右端点
            {
                if(i == next)
                    return -1;  // 表示下一座最长的桥已经到达了，但是还没出循环，意味着走不到终点
                cur = next;
                ans++;
            }
        }
        return ans;
    }

    // Z 算法
    vector<int> calcZ(const string &s)
    {
        int n = s.size();
        vector<int> z(n, 0);
        // z[0] 无意义，因为以 0 起始的字符串总是整个字符串的前缀
        for(int i = 1, left = 0, right = 0; i < n; i++)
        {
            if(i <= right)
                z[i] = min(z[i - left], right - i + 1);
            while(i + z[i] < n && s[z[i]] == s[i + z[i]])
            {
                left = i;
                right = i + z[i];
                z[i]++;
            }
        }
        return z;
    }
public:
    int minValidStrings(vector<string>& words, string target)
    {
        // 方法一: Z 函数 + 跳跃游戏
        // int n = target.size();
        // vector<int> maxJumps(n);
        // for(auto &word : words)
        // {
        //     // 计算 target 每个字符最长能够走多远
        //     vector<int> z = calcZ(word + "#" + target);
        //     int m = word.size() + 1;
        //     for(int i = 0; i < n; i++)
        //         maxJumps[i] = max(maxJumps[i], z[m + i]);
        // }
        // return jump(maxJumps);

        // 方法二: 字符串哈希 + 二分 + 跳跃游戏
        int base = 13331, mod = 998244353;
        Hashing hashing(target, base, mod);
        int m = 0, n = target.size();
        for (const string& word : words) 
            m = max(m, (int) word.size());

        // 存储每种长度前缀的哈希值
        vector<unordered_set<long long>> s(m + 1);
        for (const string& w : words)
        {
            long long h = 0;
            for (int j = 0; j < w.size(); j++) 
            {
                h = (h * base + w[j]) % mod;
                s[j + 1].insert(h);
            }
        }

        auto f = [&](int i) -> int
        {
            // 二分
            int l = 0, r = min(n - i, m);
            while (l < r)
            {
                int mid = (l + r + 1) >> 1;
                long long sub = hashing.query(i + 1, i + mid);
                if (s[mid].count(sub))
                {
                    l = mid;
                }
                else
                {
                    r = mid - 1;
                }
            }
            return l;
        };

        // 跳跃游戏变形
        int ans = 0, last = 0, mx = 0;
        for (int i = 0; i < n; i++)
        {
            int dist = f(i);
            mx = max(mx, i + dist);
            if (i == last) 
            {
                if (i == mx)
                    return -1;
                last = mx;
                ans++;
            }
        }
        return ans;
    }
};